import matplotlib.pyplot as plt

# Cohen-Sutherland 算法
INSIDE = 0  # 0000
LEFT = 1    # 0001
RIGHT = 2   # 0010
BOTTOM = 4  # 0100
TOP = 8     # 1000

def compute_outcode(x, y, rect):
    xmin, ymin, xmax, ymax = rect
    code = INSIDE
    if x < xmin:
        code |= LEFT
    elif x > xmax:
        code |= RIGHT
    if y < ymin:
        code |= BOTTOM
    elif y > ymax:
        code |= TOP
    return code

def cohen_sutherland_clip(line, rect):
    x0, y0, x1, y1 = line
    xmin, ymin, xmax, ymax = rect
    outcode0 = compute_outcode(x0, y0, rect)
    outcode1 = compute_outcode(x1, y1, rect)
    accept = False

    while True:
        if not (outcode0 | outcode1):  # Bitwise OR is 0. Trivially accept
            accept = True
            break
        elif outcode0 & outcode1:  # Bitwise AND is not 0. Trivially reject
            break
        else:
            x, y = 0.0, 0.0
            outcode_out = outcode0 if outcode0 else outcode1
            if outcode_out & TOP:
                x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0)
                y = ymax
            elif outcode_out & BOTTOM:
                x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0)
                y = ymin
            elif outcode_out & RIGHT:
                y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0)
                x = xmax
            elif outcode_out & LEFT:
                y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0)
                x = xmin

            if outcode_out == outcode0:
                x0, y0 = x, y
                outcode0 = compute_outcode(x0, y0, rect)
            else:
                x1, y1 = x, y
                outcode1 = compute_outcode(x1, y1, rect)

    if accept:
        return (x0, y0, x1, y1)
    else:
        return None

# 题给数据
line = (10, 45, 70, 75)
clip_rect = (20, 20, 120, 70)
clipped_line = cohen_sutherland_clip(line, clip_rect)
print(clipped_line)

# 可视化
fig, ax = plt.subplots()
ax.set_xlim(0, 130)
ax.set_ylim(0, 80)

# 绘制裁剪窗口
rect_x = [clip_rect[0], clip_rect[2], clip_rect[2], clip_rect[0], clip_rect[0]]
rect_y = [clip_rect[1], clip_rect[1], clip_rect[3], clip_rect[3], clip_rect[1]]
ax.plot(rect_x, rect_y, 'k-', label='Clipping Window')

# 绘制原始线段
ax.plot([line[0], line[2]], [line[1], line[3]], 'r--', label='Original Line')

# 绘制裁剪后的线段
if clipped_line:
    ax.plot([clipped_line[0], clipped_line[2]], [clipped_line[1], clipped_line[3]], 'g-', label='Clipped Line')

# 添加图例
ax.legend()
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Cohen-Sutherland Line Clipping')
plt.grid(True)
plt.show()
